A user can perform a query search to lookup information stored on a device. A query search begins with a client on the device receiving the query string, which is sent to a local search module. The client can be one of variety of applications that support local search (e.g., mail, media, calendar, and the file browser). The local search module receives query string and searches a search index for results that match this query string. The local search module then returns the results to the client. In order to assist the user on the client, the search server may also suggest query completions based on a partially entered query string. The suggested query completions are presented to the user, so that the user can choose one of the query completions as the string to be used for the search.
The suggested query completions, however, do not take advantage of the structure that is available in the local search index, because the suggested query completions match the words in the query prefix. A user may specify, by using keywords, that specific words in the query prefix match specific metadata, but this format is difficult to use.